//https://www.nowcoder.com/practice/41c399fdb6004b31a6cbb047c641ed8a
//环形链表的约瑟夫问题
//编号为 1 到 n 的 n 个人围成一圈。从编号为 1 的人开始报数，报到 m 的人离开。
//下一个人继续从 1 开始报数。
//n-1 轮结束以后，只剩下一个人，问最后留下的这个人编号是多少？

//标准解答
typedef struct ListNode ListNode;

ListNode* BuyNode(int x)
{
    ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
    newnode->val = x;
    newnode->next = NULL;
    return newnode;
}

ListNode* CreatCircle(int n)
{
    ListNode* phead = BuyNode(1);
    ListNode* ptail = phead;
    for(int i = 2; i <= n; i++)
    {
        ListNode* newnode = BuyNode(i);
        ptail->next = newnode;
        ptail = ptail->next;
    }

    ptail->next = phead;
    return ptail;
}

int ysf1(int n, int m ) {
    // write code here
    if(n == 1)
    return 1;
    ListNode* prev = CreatCircle(n);
    ListNode* pcur = prev->next;

    int count = 1;
    while(pcur != pcur->next)
    {
        if(count == m)
        {
            prev->next = pcur->next;
            free(pcur);
            pcur = prev->next;
            count = 1;
        }
        else 
        {
            prev = pcur;
            pcur = pcur->next;
            count++;
        }
    }

    return pcur->val;
}

//666
int ysf2(int n, int m) 
{
    int res = 0;
    for(int i = 2; i <= n; i++)
    {
        res = (res + m) % i;
    }
    return res + 1;
}